1. Field of the Invention
The invention relates generally to the field of multipliers. More specifically, the invention is directed towards a 4-2 compressor of a multiplier having transfer-gate type exclusive OR and exclusive NOR gates.
2. Description of Related Art
In general, digital signal processors (DSP's) may be equipped with a multiply-accumulate module for the execution of multiplication instructions, such as multiplying a multiplicand X by a multiplier Y. The speed of the multiply-accumulate module may affect the operation frequency of the DSP such that increasing the speed of the multiply-accumulate module also may increase the operation frequency of the DSP. Some known multiply-accumulate modules may include a multiplier, an adder for the multiplier, and a saturation module. In some known multiply-accumulate modules, the multiplier may account for about half of the delay in the critical path of the multiply-accumulate module. Consequently, increasing the speed of the multiplier substantially may increase the overall speed of the multiply-accumulate module.
Some known multipliers may include at least two (2) stages. In the first stage, partial products of each bit of multiplier Y may be generated. The number of partial products depends on the number of bits of multiplier Y. For example, when multiplier Y is a 32-bit multiplier, thirty-two partial products may be generated. Similarly, when multiplier Y is a 17-bit multiplier, seventeen partial products may be generated. Moreover, in order to multiply multiplicand X by multiplier Y, the partial products are summed. Consequently, as the number of partial products increases, the number of summation steps also increases. In order to reduce the number of summation steps, some known multipliers may employ one of the known Booth Algorithms, e.g., the secondary Booth algorithm. The Booth algorithm may rewrite or encode the bits of multiplier Y, such that the number of partial products may be reduced. For example, when the secondary Booth algorithm is employed, the number of partial products to be summed may be reduced by a factor of two.
In the second stage, some known multipliers may sum the partial products. Moreover, to sum the partial products, the multipliers may sum the partial products in a Wallace tree. Some known Wallace trees may comprise a plurality of full adders. Alternatively, other known Wallace trees may comprise a plurality of compressors, such as a plurality of 4-2 compressors and full adders. The 4-2 compressors may count the number of “1's” in their respective inputs. For example, referring to FIG. 1, a flow chart of a known 54-bit multiplier 100 is shown. Multiplier 100 may comprise a Booth encoding circuit 102, which may generate twenty-seven partial products, which may be inputted into a Wallace tree 104. Specifically, four bit products from four partial products and one carry bit input may be inputted into each 4-2 compressor 104a–104g. A bit product may be defined as any single bit in a partial product. Compressors 104a–104g may generate a plurality of output signals, which may be inputted into 4-2 compressors 104h–104j, respectively. The above-described summation process may descend to the bottom of Wallace tree 104, such that 4-2 compressor 104m may generate a final summation output and carry bit outputs.
The number of 4-2 compressors employed in Wallace tree 104 may depend on the number partial products generated by the Booth encoding circuit. In addition, each 4-2 compressor may receive five inputs. Each 4-2 compressor may generate three outputs, such as a summation output and two carry bit outputs. For example, referring to FIGS. 2–6, in some known 4-2 compressors, bit products from partial products Ai, Bi, Ci, and Di, along with carry bit Xi, may be inputted into the compressor, which may generate a summation output So, a first carry bit Co, and second carry bit Xo. As shown in FIG. 7, for any 4-2 compressor, there are nine possible truth table patterns. Moreover, using known techniques, these patterns may be converted, such that they may be expressed as a logical formula(s), and 4-2 compressors may be designed to implement such logical expressions. For example, summation output So may be logically expressed as So=((Bi⊕Ci)⊕Di)⊕(Ai⊕Xi), where ⊕ is the logic symbol for an exclusive OR (XOR) logic gate. Alternatively, summation output So may be logically expressed as So=((Bi⊕Ci)⊕(Di⊕Ai))⊕Xi. In addition, carry bit Co may be logically expressed as Co=((Ai⊕Xi)·((Bi⊕Ci)⊕Di))+{overscore ((Ai⊕Xi))}·Ai, where · is the logic symbol for AND, + is the logic symbol for an OR gate, and where the line bar is the logical symbol for NOT. Alternatively, the carry bit Co may be logically expressed as Co={overscore (((Bi⊕Ci)⊕(Di⊕Ai)))}{overscore (((Bi⊕Ci)⊕(Di⊕Ai)))}·Xi+((Bi⊕Ci)⊕(Di⊕Ai))·Ai. Moreover, carry bit Xo may be expressed as Xo=(Bi⊕Ci)·Di+({overscore (Bi⊕Ci)})·Bi.
Each of the known compressors shown in FIGS. 2–6, is designed to implement the above-described logical expressions for So, Co, and Xo. For example, referring to FIG. 2, a 4-2 compressor 200 may employ pass transistor logic exclusive OR (XOR) gates and pass transistor logic exclusive NOT OR (XNOR) gates to implement the above-described logical expressions. The term “pass transistor logic XOR gate” may be defined as employing a circuit as shown in FIG. 8a to generate an XOR output. Similarly, the term “pass transistor logic XNOR gate” may be defined as employing a circuit as shown in FIG. 8b to generate an XNOR output. Moreover, 4-2 compressor 200 also may employ transfer gate logic XOR gates and transfer gate logic XNOR gates to implement the above-described logical expressions. The term “transfer gate logic XOR gate” may be defined as employing a circuit as shown in FIG. 9a to generate an XOR output. Similarly, the term “transfer gate logic XNOR gate” may be defined as employing a circuit as shown in FIG. 9b to generate an XNOR output. Compressor 200 may include logic stages 202, 204, 206, and 208, which may be XOR, or XNOR stages. Compressor 200 also may include a plurality of transistor paths between each of the inputs and each of the outputs. A path may be defined as the electrical route over which a particular input signal must travel in order to reach a particular output. For example, in order to reach output So, input signal Bi may flow through an inverter 210, a switch 212, such as a CMOS switch, a switch 215, an inverter 216, an inverter 218, a switch 220, and an inverter 222. Thus, for this particular path (A), input signal Bi flows through seven transistor gates, such that the “transistor stage level” for path (A) is seven. Moreover, input signal Bi also flows through logic stages 202, 204, and 208, such that the “logic stage level” for path (A) is three. However, in order to reach output So, input signal Bi also may flow through a switch 230, switch 214, inverter 216, inverter 218, switch 220, and inverter 222. Thus for this particular path (B), although the logic stage number also is three, input signal Bi only flows through six transistor gates, such that the transistor stage level for path (B) is six. However, each of the inputs Ai, Bi, Ci, Di, and Xi may have a path or multiple paths to at least one of the outputs.
A first compressor “critical transistor stage path” may be defined as the path having the greatest transistor stage level between an input and an output within first compressor 200. Similarly, a first compressor “critical logic stage path” may be defined as the path having the greatest logic stage level between an input and an output within first compressor 200. Decreasing the first compressor critical transistor stage path level may increase the speed of the multiplier. Similarly, decreasing the first compressor critical logic stage path level also may increase the speed of the multiplier. However, each 4-2 compressor may have a plurality of first compressor critical transistor stage paths and a plurality of first compressor critical logic stage paths, or alternatively, may have a single first compressor critical transistor stage path. For example, in compressor 200, path (A) is a first compressor critical transistor stage path and also is a first compressor critical logic stage path because for path (A), the transistor stage level is seven and the logic stage level is three, and no other paths between an input and an output have a greater transistor stage level or a greater logic stage level. Path (B) is not a first compressor critical transistor stage path because for path (B), the transistor stage level only is six, and as such, the transistor stage level for path (A) is greater than the transistor stage level for path (B). However, path (B) is a first compressor critical logic stage path because the logic stage level for path (B) is three, and as such, the logic stage level for path (B) is the same as the transistor stage level for path (A).
In addition, the first carry bit output Xo from an initial compressor 200 may be connected to the carry bit input Xi of a successive compressor 200 in the Wallace tree. Consequently, in addition to having at least one first compressor critical logic stage path and at least one first compressor critical transistor stage path, each compressor 200 also has at least one successive compressor critical transistor stage path and at least one successive compressor critical logic stage path. For example, in compressor 200, carry bit output Xo may be defined by inputs Bi, Ci, and Di. Input signal Bi may flow through inverter 210, switch 212, a switch 224, and an inverter 226. The first carry bit output Xo of first compressor 200 then may be connected to the carry bit input of successive compressor 200, such that carry bit input Xi may help generate summation output So and carry bit output Co. For example, carry bit output Xo may flow through a switch 228, a switch 232, and inverter 222. This successive path (C) from Bi and Xo of first compressor 200 to Xi and So of successive compressor 200 has a transistor path level of seven. In addition, successive path (C) flows through stages 202 and 204 of first compressor 200 and stages 206 and 208 of successive compressor 200. Consequently, successive path (C) has a logic stage level of four. Similarly, input signal Ci may flow through switch 212, switch 224, and inverter 226. The first carry bit output Xo of first compressor 200 then may be connected to the carry bit input of successive compressor 200, such that carry bit input Xi may help generate summation output So. For example, carry bit output Xo may flow through switch 228, switch 232, and inverter 222. This successive path (D) from Ci and Xo of first compressor 200 to Xi and So of successive compressor 200 has a transistor path level of six. In addition, successive path (D) flows through stages 202 and 204 of first compressor 200 and stages 206 and 208 of successive compressor 200. Consequently, successive path (D) also has a logic stage level of four.
A successive compressor “critical transistor stage path” may be defined as the path having the greatest transistor stage level from one of the inputs of first compressor 200 to first compressor 200 carry bit output Xo and further to successive compressor 200 summation output So or carry bit output Co. Similarly, a successive compressor “critical logic stage path” may be defined as the path having the greatest logic stage level from one of the inputs of first compressor 200 to first compressor 200 carry bit output Xo and further to successive compressor 200 summation output So or carry bit output Co. Decreasing the successive compressor critical transistor stage path level may increase the speed of the multiplier. Similarly, decreasing the successive compressor critical logic stage path level also may increase the speed of the multiplier. However, each 4-2 compressor may have a plurality of successive compressor critical transistor stage paths and a plurality of successive compressor critical logic stage paths, or alternatively, may have a single successive compressor critical transistor stage path. For example, in compressor 200, successive path (C) is a successive compressor critical transistor stage path and also is a successive compressor critical logic stage path because for successive path (C) the transistor stage level is seven and the logic stage level is four. Successive path (D) is not a successive compressor critical transistor stage path because for successive path (D) the transistor stage level only is six. However, successive path (D) is a successive compressor critical logic stage path because the logic stage level is four.
Consequently, for compressor 200, the first compressor critical transistor stage path level is seven, the successive compressor critical transistor stage path level is seven, the first compressor critical logic stage path level is three, and the successive compressor critical logic stage path level is four.
Referring to FIG. 3, another known 4-2 compressor 300 is shown. Compressor 300 may employ transfer gate logic XOR gates, as shown in FIG. 9a, and transfer gate logic XNOR gates, as shown in FIG. 9b, to implement the above-described logical expressions. Compressor 300 may include logic stages 302, 304, 306, and 308, which may be XOR or XNOR stages. In compressor 300, input signal Bi may flow through an inverter 310, a switch 312, a switch 314, an inverter 316, an inverter 318, a switch 320, and an inverter 322. Thus, for this particular path (E), the transistor stage level is seven. In addition, no other paths in compressor 300 have a transistor stage level which is greater than seven. Consequently, path (E) is a first compressor critical transistor stage path and the first compressor critical transistor stage path is seven. Path (E) also may flow through logic stages 302, 304, and 308. Thus, the logic stage level for path (E) is three. Moreover, path (E) also is a first compressor 300 critical logic stage path. Consequently, the first compressor critical logic stage path is three.
Input signal Ci may flow through an inverter 324, a switch 326, a switch 328, and an inverter 330. Moreover, when first carry bit output Xo is connected to carry bit input of a successive compressor 300, input signal Ci also flows through an inverter 332, a switch 334, a switch 337, and an inverter 338 to generate second carry bit output Co. Thus, for this particular successive path (F), the transistor stage level is eight. In addition, no other paths have a successive transistor stage level greater than eight, such that successive path (F) also is a successive compressor 300 critical transistor stage path. Consequently, the successive compressor critical transistor stage path is eight. Successive path (F) also may flow through logic stages 302, 304, 306, and 308. Thus, the logic stage level for successive path (F) is four. Moreover, successive path (F) also is a successive compressor 300 critical logic stage path. Consequently, the successive compressor critical logic stage path is four.
Consequently, for compressor 300, the first compressor critical transistor stage path level is seven, the successive compressor critical transistor stage path level is eight, the first compressor critical logic stage path level is three, and the successive compressor critical logic stage path level is four.
Referring to FIG. 4, another known 4-2 compressor 400 is shown. Compressor 400 may employ transfer gate logic XOR gates, as shown in FIG. 9a, and transfer gate logic XNOR gates, as shown in FIG. 9b, to implement the above-described logical expressions. Compressor 400 may include logic stages 402, 404, and 406, which may be XOR or XNOR stages. In compressor 400, input signal Bi may flow through an inverter 408, a switch 410, a switch 412, a switch 414, an inverter 416, and an inverter 418. Thus, for this particular path (G), the transistor stage level is six. In addition, no other paths have a transistor stage level greater than six, such that path (G) also is a first compressor 400 critical transistor stage path. Consequently, the first compressor critical transistor stage path is six. Path (G) also may flow through logic stages 402, 404, and 406. Thus, the logic stage level for path (G) is three. Moreover, path (G) also is a first compressor 400 critical logic stage path. Consequently, the first compressor critical logic stage path is three.
Input signal Bi also may flow through inverter 408, switch 410, a switch 420, an inverter 422 and an inverter 424. Moreover, when first carry bit output Xo is connected to carry bit input of a successive compressor 400, input signal Bi also flows through an inverter 426, switch 414, inverter 416, and inverter 418 to generate summation output So. Thus, for this particular successive path (H), the transistor stage level is nine. In addition, no other paths have a successive transistor stage level greater than nine, such that successive path (H) also is a successive compressor 400 critical transistor stage path. Consequently, the successive compressor critical transistor stage path is nine. Successive path (H) also may flow through logic stages 402, 404, and 406. Thus, the logic stage level for successive path (H) is three. Moreover, successive path (H) also is a successive compressor 400 critical logic stage path. Consequently, the successive compressor critical logic stage path is three.
Consequently, for compressor 400, the first compressor critical transistor stage path level is six, the successive compressor critical transistor stage path level is nine, the first compressor critical logic stage path level is three, and the successive compressor critical logic stage path level is three.
Referring to FIG. 5, another known 4-2 compressor 500 is shown. Compressor 500 may employ tri-state buffers to implement the above-described logical expressions, and may include logic stages 502, 504, and 506. Moreover for compressor 500, the first compressor critical transistor stage path level is eight, the successive compressor critical transistor stage path level is eight, the first compressor critical logic stage path level is three, and the successive compressor critical logic stage path level is three.
Referring to FIG. 6, another known 4-2 compressor 600 is shown. Compressor 600 may employ a different type of transfer gate logic XOR gates and transfer gate logic XNOR gates to implement the above-described logical expressions, and may include logic stages 602, 604, and 606. Moreover for compressor 600, the first compressor critical transistor stage path level is six, the successive compressor critical transistor stage path level is nine, the first compressor critical logic stage path level is three, and the successive compressor critical logic stage path level is three.